# https://leetcode.com/problems/rotated-digits


class Solution(object):
    def isvalid(self, n):
        str_n = set(str(n))
        converter_chage = {'2', '5', '6', '9'}
        converter_other = {'3', '4', '7'}
        if str_n & converter_other:
            return False
        elif str_n & converter_chage:
            return True
        else:
            return False

    def rotatedDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        output = 0
        for i in range(1, N + 1):
            if self.isvalid(i):
                output += 1
        return output


# %%
# a = []
# for i in range(1, 10001):
#     if Solution().isvalid(i):
#         print(i, end=',')
N = 100

nums = [2, 5, 6, 9, 12, 15, 16, 19, 20, 21, 22, 25, 26, 28, 29, 50, 51, 52, 55, 56, 58, 59, 60, 61, 62, 65, 66, 68, 69,
        82,
        85, 86, 89, 90, 91, 92, 95, 96, 98, 99, 102, 105, 106, 109, 112, 115, 116, 119, 120, 121, 122, 125, 126, 128,
        129,
        150, 151, 152, 155, 156, 158, 159, 160, 161, 162, 165, 166, 168, 169, 182, 185, 186, 189, 190, 191, 192, 195,
        196,
        198, 199, 200, 201, 202, 205, 206, 208, 209, 210, 211, 212, 215, 216, 218, 219, 220, 221, 222, 225, 226, 228,
        229,
        250, 251, 252, 255, 256, 258, 259, 260, 261, 262, 265, 266, 268, 269, 280, 281, 282, 285, 286, 288, 289, 290,
        291,
        292, 295, 296, 298, 299, 500, 501, 502, 505, 506, 508, 509, 510, 511, 512, 515, 516, 518, 519, 520, 521, 522,
        525,
        526, 528, 529, 550, 551, 552, 555, 556, 558, 559, 560, 561, 562, 565, 566, 568, 569, 580, 581, 582, 585, 586,
        588,
        589, 590, 591, 592, 595, 596, 598, 599, 600, 601, 602, 605, 606, 608, 609, 610, 611, 612, 615, 616, 618, 619,
        620,
        621, 622, 625, 626, 628, 629, 650, 651, 652, 655, 656, 658, 659, 660, 661, 662, 665, 666, 668, 669, 680, 681,
        682,
        685, 686, 688, 689, 690, 691, 692, 695, 696, 698, 699, 802, 805, 806, 809, 812, 815, 816, 819, 820, 821, 822,
        825,
        826, 828, 829, 850, 851, 852, 855, 856, 858, 859, 860, 861, 862, 865, 866, 868, 869, 882, 885, 886, 889, 890,
        891,
        892, 895, 896, 898, 899, 900, 901, 902, 905, 906, 908, 909, 910, 911, 912, 915, 916, 918, 919, 920, 921, 922,
        925,
        926, 928, 929, 950, 951, 952, 955, 956, 958, 959, 960, 961, 962, 965, 966, 968, 969, 980, 981, 982, 985, 986,
        988,
        989, 990, 991, 992, 995, 996, 998, 999, 1002, 1005, 1006, 1009, 1012, 1015, 1016, 1019, 1020, 1021, 1022, 1025,
        1026, 1028, 1029, 1050, 1051, 1052, 1055, 1056, 1058, 1059, 1060, 1061, 1062, 1065, 1066, 1068, 1069, 1082,
        1085,
        1086, 1089, 1090, 1091, 1092, 1095, 1096, 1098, 1099, 1102, 1105, 1106, 1109, 1112, 1115, 1116, 1119, 1120,
        1121,
        1122, 1125, 1126, 1128, 1129, 1150, 1151, 1152, 1155, 1156, 1158, 1159, 1160, 1161, 1162, 1165, 1166, 1168,
        1169,
        1182, 1185, 1186, 1189, 1190, 1191, 1192, 1195, 1196, 1198, 1199, 1200, 1201, 1202, 1205, 1206, 1208, 1209,
        1210,
        1211, 1212, 1215, 1216, 1218, 1219, 1220, 1221, 1222, 1225, 1226, 1228, 1229, 1250, 1251, 1252, 1255, 1256,
        1258,
        1259, 1260, 1261, 1262, 1265, 1266, 1268, 1269, 1280, 1281, 1282, 1285, 1286, 1288, 1289, 1290, 1291, 1292,
        1295,
        1296, 1298, 1299, 1500, 1501, 1502, 1505, 1506, 1508, 1509, 1510, 1511, 1512, 1515, 1516, 1518, 1519, 1520,
        1521,
        1522, 1525, 1526, 1528, 1529, 1550, 1551, 1552, 1555, 1556, 1558, 1559, 1560, 1561, 1562, 1565, 1566, 1568,
        1569,
        1580, 1581, 1582, 1585, 1586, 1588, 1589, 1590, 1591, 1592, 1595, 1596, 1598, 1599, 1600, 1601, 1602, 1605,
        1606,
        1608, 1609, 1610, 1611, 1612, 1615, 1616, 1618, 1619, 1620, 1621, 1622, 1625, 1626, 1628, 1629, 1650, 1651,
        1652,
        1655, 1656, 1658, 1659, 1660, 1661, 1662, 1665, 1666, 1668, 1669, 1680, 1681, 1682, 1685, 1686, 1688, 1689,
        1690,
        1691, 1692, 1695, 1696, 1698, 1699, 1802, 1805, 1806, 1809, 1812, 1815, 1816, 1819, 1820, 1821, 1822, 1825,
        1826,
        1828, 1829, 1850, 1851, 1852, 1855, 1856, 1858, 1859, 1860, 1861, 1862, 1865, 1866, 1868, 1869, 1882, 1885,
        1886,
        1889, 1890, 1891, 1892, 1895, 1896, 1898, 1899, 1900, 1901, 1902, 1905, 1906, 1908, 1909, 1910, 1911, 1912,
        1915,
        1916, 1918, 1919, 1920, 1921, 1922, 1925, 1926, 1928, 1929, 1950, 1951, 1952, 1955, 1956, 1958, 1959, 1960,
        1961,
        1962, 1965, 1966, 1968, 1969, 1980, 1981, 1982, 1985, 1986, 1988, 1989, 1990, 1991, 1992, 1995, 1996, 1998,
        1999,
        2000, 2001, 2002, 2005, 2006, 2008, 2009, 2010, 2011, 2012, 2015, 2016, 2018, 2019, 2020, 2021, 2022, 2025,
        2026,
        2028, 2029, 2050, 2051, 2052, 2055, 2056, 2058, 2059, 2060, 2061, 2062, 2065, 2066, 2068, 2069, 2080, 2081,
        2082,
        2085, 2086, 2088, 2089, 2090, 2091, 2092, 2095, 2096, 2098, 2099, 2100, 2101, 2102, 2105, 2106, 2108, 2109,
        2110,
        2111, 2112, 2115, 2116, 2118, 2119, 2120, 2121, 2122, 2125, 2126, 2128, 2129, 2150, 2151, 2152, 2155, 2156,
        2158,
        2159, 2160, 2161, 2162, 2165, 2166, 2168, 2169, 2180, 2181, 2182, 2185, 2186, 2188, 2189, 2190, 2191, 2192,
        2195,
        2196, 2198, 2199, 2200, 2201, 2202, 2205, 2206, 2208, 2209, 2210, 2211, 2212, 2215, 2216, 2218, 2219, 2220,
        2221,
        2222, 2225, 2226, 2228, 2229, 2250, 2251, 2252, 2255, 2256, 2258, 2259, 2260, 2261, 2262, 2265, 2266, 2268,
        2269,
        2280, 2281, 2282, 2285, 2286, 2288, 2289, 2290, 2291, 2292, 2295, 2296, 2298, 2299, 2500, 2501, 2502, 2505,
        2506,
        2508, 2509, 2510, 2511, 2512, 2515, 2516, 2518, 2519, 2520, 2521, 2522, 2525, 2526, 2528, 2529, 2550, 2551,
        2552,
        2555, 2556, 2558, 2559, 2560, 2561, 2562, 2565, 2566, 2568, 2569, 2580, 2581, 2582, 2585, 2586, 2588, 2589,
        2590,
        2591, 2592, 2595, 2596, 2598, 2599, 2600, 2601, 2602, 2605, 2606, 2608, 2609, 2610, 2611, 2612, 2615, 2616,
        2618,
        2619, 2620, 2621, 2622, 2625, 2626, 2628, 2629, 2650, 2651, 2652, 2655, 2656, 2658, 2659, 2660, 2661, 2662,
        2665,
        2666, 2668, 2669, 2680, 2681, 2682, 2685, 2686, 2688, 2689, 2690, 2691, 2692, 2695, 2696, 2698, 2699, 2800,
        2801,
        2802, 2805, 2806, 2808, 2809, 2810, 2811, 2812, 2815, 2816, 2818, 2819, 2820, 2821, 2822, 2825, 2826, 2828,
        2829,
        2850, 2851, 2852, 2855, 2856, 2858, 2859, 2860, 2861, 2862, 2865, 2866, 2868, 2869, 2880, 2881, 2882, 2885,
        2886,
        2888, 2889, 2890, 2891, 2892, 2895, 2896, 2898, 2899, 2900, 2901, 2902, 2905, 2906, 2908, 2909, 2910, 2911,
        2912,
        2915, 2916, 2918, 2919, 2920, 2921, 2922, 2925, 2926, 2928, 2929, 2950, 2951, 2952, 2955, 2956, 2958, 2959,
        2960,
        2961, 2962, 2965, 2966, 2968, 2969, 2980, 2981, 2982, 2985, 2986, 2988, 2989, 2990, 2991, 2992, 2995, 2996,
        2998,
        2999, 5000, 5001, 5002, 5005, 5006, 5008, 5009, 5010, 5011, 5012, 5015, 5016, 5018, 5019, 5020, 5021, 5022,
        5025,
        5026, 5028, 5029, 5050, 5051, 5052, 5055, 5056, 5058, 5059, 5060, 5061, 5062, 5065, 5066, 5068, 5069, 5080,
        5081,
        5082, 5085, 5086, 5088, 5089, 5090, 5091, 5092, 5095, 5096, 5098, 5099, 5100, 5101, 5102, 5105, 5106, 5108,
        5109,
        5110, 5111, 5112, 5115, 5116, 5118, 5119, 5120, 5121, 5122, 5125, 5126, 5128, 5129, 5150, 5151, 5152, 5155,
        5156,
        5158, 5159, 5160, 5161, 5162, 5165, 5166, 5168, 5169, 5180, 5181, 5182, 5185, 5186, 5188, 5189, 5190, 5191,
        5192,
        5195, 5196, 5198, 5199, 5200, 5201, 5202, 5205, 5206, 5208, 5209, 5210, 5211, 5212, 5215, 5216, 5218, 5219,
        5220,
        5221, 5222, 5225, 5226, 5228, 5229, 5250, 5251, 5252, 5255, 5256, 5258, 5259, 5260, 5261, 5262, 5265, 5266,
        5268,
        5269, 5280, 5281, 5282, 5285, 5286, 5288, 5289, 5290, 5291, 5292, 5295, 5296, 5298, 5299, 5500, 5501, 5502,
        5505,
        5506, 5508, 5509, 5510, 5511, 5512, 5515, 5516, 5518, 5519, 5520, 5521, 5522, 5525, 5526, 5528, 5529, 5550,
        5551,
        5552, 5555, 5556, 5558, 5559, 5560, 5561, 5562, 5565, 5566, 5568, 5569, 5580, 5581, 5582, 5585, 5586, 5588,
        5589,
        5590, 5591, 5592, 5595, 5596, 5598, 5599, 5600, 5601, 5602, 5605, 5606, 5608, 5609, 5610, 5611, 5612, 5615,
        5616,
        5618, 5619, 5620, 5621, 5622, 5625, 5626, 5628, 5629, 5650, 5651, 5652, 5655, 5656, 5658, 5659, 5660, 5661,
        5662,
        5665, 5666, 5668, 5669, 5680, 5681, 5682, 5685, 5686, 5688, 5689, 5690, 5691, 5692, 5695, 5696, 5698, 5699,
        5800,
        5801, 5802, 5805, 5806, 5808, 5809, 5810, 5811, 5812, 5815, 5816, 5818, 5819, 5820, 5821, 5822, 5825, 5826,
        5828,
        5829, 5850, 5851, 5852, 5855, 5856, 5858, 5859, 5860, 5861, 5862, 5865, 5866, 5868, 5869, 5880, 5881, 5882,
        5885,
        5886, 5888, 5889, 5890, 5891, 5892, 5895, 5896, 5898, 5899, 5900, 5901, 5902, 5905, 5906, 5908, 5909, 5910,
        5911,
        5912, 5915, 5916, 5918, 5919, 5920, 5921, 5922, 5925, 5926, 5928, 5929, 5950, 5951, 5952, 5955, 5956, 5958,
        5959,
        5960, 5961, 5962, 5965, 5966, 5968, 5969, 5980, 5981, 5982, 5985, 5986, 5988, 5989, 5990, 5991, 5992, 5995,
        5996,
        5998, 5999, 6000, 6001, 6002, 6005, 6006, 6008, 6009, 6010, 6011, 6012, 6015, 6016, 6018, 6019, 6020, 6021,
        6022,
        6025, 6026, 6028, 6029, 6050, 6051, 6052, 6055, 6056, 6058, 6059, 6060, 6061, 6062, 6065, 6066, 6068, 6069,
        6080,
        6081, 6082, 6085, 6086, 6088, 6089, 6090, 6091, 6092, 6095, 6096, 6098, 6099, 6100, 6101, 6102, 6105, 6106,
        6108,
        6109, 6110, 6111, 6112, 6115, 6116, 6118, 6119, 6120, 6121, 6122, 6125, 6126, 6128, 6129, 6150, 6151, 6152,
        6155,
        6156, 6158, 6159, 6160, 6161, 6162, 6165, 6166, 6168, 6169, 6180, 6181, 6182, 6185, 6186, 6188, 6189, 6190,
        6191,
        6192, 6195, 6196, 6198, 6199, 6200, 6201, 6202, 6205, 6206, 6208, 6209, 6210, 6211, 6212, 6215, 6216, 6218,
        6219,
        6220, 6221, 6222, 6225, 6226, 6228, 6229, 6250, 6251, 6252, 6255, 6256, 6258, 6259, 6260, 6261, 6262, 6265,
        6266,
        6268, 6269, 6280, 6281, 6282, 6285, 6286, 6288, 6289, 6290, 6291, 6292, 6295, 6296, 6298, 6299, 6500, 6501,
        6502,
        6505, 6506, 6508, 6509, 6510, 6511, 6512, 6515, 6516, 6518, 6519, 6520, 6521, 6522, 6525, 6526, 6528, 6529,
        6550,
        6551, 6552, 6555, 6556, 6558, 6559, 6560, 6561, 6562, 6565, 6566, 6568, 6569, 6580, 6581, 6582, 6585, 6586,
        6588,
        6589, 6590, 6591, 6592, 6595, 6596, 6598, 6599, 6600, 6601, 6602, 6605, 6606, 6608, 6609, 6610, 6611, 6612,
        6615,
        6616, 6618, 6619, 6620, 6621, 6622, 6625, 6626, 6628, 6629, 6650, 6651, 6652, 6655, 6656, 6658, 6659, 6660,
        6661,
        6662, 6665, 6666, 6668, 6669, 6680, 6681, 6682, 6685, 6686, 6688, 6689, 6690, 6691, 6692, 6695, 6696, 6698,
        6699,
        6800, 6801, 6802, 6805, 6806, 6808, 6809, 6810, 6811, 6812, 6815, 6816, 6818, 6819, 6820, 6821, 6822, 6825,
        6826,
        6828, 6829, 6850, 6851, 6852, 6855, 6856, 6858, 6859, 6860, 6861, 6862, 6865, 6866, 6868, 6869, 6880, 6881,
        6882,
        6885, 6886, 6888, 6889, 6890, 6891, 6892, 6895, 6896, 6898, 6899, 6900, 6901, 6902, 6905, 6906, 6908, 6909,
        6910,
        6911, 6912, 6915, 6916, 6918, 6919, 6920, 6921, 6922, 6925, 6926, 6928, 6929, 6950, 6951, 6952, 6955, 6956,
        6958,
        6959, 6960, 6961, 6962, 6965, 6966, 6968, 6969, 6980, 6981, 6982, 6985, 6986, 6988, 6989, 6990, 6991, 6992,
        6995,
        6996, 6998, 6999, 8002, 8005, 8006, 8009, 8012, 8015, 8016, 8019, 8020, 8021, 8022, 8025, 8026, 8028, 8029,
        8050,
        8051, 8052, 8055, 8056, 8058, 8059, 8060, 8061, 8062, 8065, 8066, 8068, 8069, 8082, 8085, 8086, 8089, 8090,
        8091,
        8092, 8095, 8096, 8098, 8099, 8102, 8105, 8106, 8109, 8112, 8115, 8116, 8119, 8120, 8121, 8122, 8125, 8126,
        8128,
        8129, 8150, 8151, 8152, 8155, 8156, 8158, 8159, 8160, 8161, 8162, 8165, 8166, 8168, 8169, 8182, 8185, 8186,
        8189,
        8190, 8191, 8192, 8195, 8196, 8198, 8199, 8200, 8201, 8202, 8205, 8206, 8208, 8209, 8210, 8211, 8212, 8215,
        8216,
        8218, 8219, 8220, 8221, 8222, 8225, 8226, 8228, 8229, 8250, 8251, 8252, 8255, 8256, 8258, 8259, 8260, 8261,
        8262,
        8265, 8266, 8268, 8269, 8280, 8281, 8282, 8285, 8286, 8288, 8289, 8290, 8291, 8292, 8295, 8296, 8298, 8299,
        8500,
        8501, 8502, 8505, 8506, 8508, 8509, 8510, 8511, 8512, 8515, 8516, 8518, 8519, 8520, 8521, 8522, 8525, 8526,
        8528,
        8529, 8550, 8551, 8552, 8555, 8556, 8558, 8559, 8560, 8561, 8562, 8565, 8566, 8568, 8569, 8580, 8581, 8582,
        8585,
        8586, 8588, 8589, 8590, 8591, 8592, 8595, 8596, 8598, 8599, 8600, 8601, 8602, 8605, 8606, 8608, 8609, 8610,
        8611,
        8612, 8615, 8616, 8618, 8619, 8620, 8621, 8622, 8625, 8626, 8628, 8629, 8650, 8651, 8652, 8655, 8656, 8658,
        8659,
        8660, 8661, 8662, 8665, 8666, 8668, 8669, 8680, 8681, 8682, 8685, 8686, 8688, 8689, 8690, 8691, 8692, 8695,
        8696,
        8698, 8699, 8802, 8805, 8806, 8809, 8812, 8815, 8816, 8819, 8820, 8821, 8822, 8825, 8826, 8828, 8829, 8850,
        8851,
        8852, 8855, 8856, 8858, 8859, 8860, 8861, 8862, 8865, 8866, 8868, 8869, 8882, 8885, 8886, 8889, 8890, 8891,
        8892,
        8895, 8896, 8898, 8899, 8900, 8901, 8902, 8905, 8906, 8908, 8909, 8910, 8911, 8912, 8915, 8916, 8918, 8919,
        8920,
        8921, 8922, 8925, 8926, 8928, 8929, 8950, 8951, 8952, 8955, 8956, 8958, 8959, 8960, 8961, 8962, 8965, 8966,
        8968,
        8969, 8980, 8981, 8982, 8985, 8986, 8988, 8989, 8990, 8991, 8992, 8995, 8996, 8998, 8999, 9000, 9001, 9002,
        9005,
        9006, 9008, 9009, 9010, 9011, 9012, 9015, 9016, 9018, 9019, 9020, 9021, 9022, 9025, 9026, 9028, 9029, 9050,
        9051,
        9052, 9055, 9056, 9058, 9059, 9060, 9061, 9062, 9065, 9066, 9068, 9069, 9080, 9081, 9082, 9085, 9086, 9088,
        9089,
        9090, 9091, 9092, 9095, 9096, 9098, 9099, 9100, 9101, 9102, 9105, 9106, 9108, 9109, 9110, 9111, 9112, 9115,
        9116,
        9118, 9119, 9120, 9121, 9122, 9125, 9126, 9128, 9129, 9150, 9151, 9152, 9155, 9156, 9158, 9159, 9160, 9161,
        9162,
        9165, 9166, 9168, 9169, 9180, 9181, 9182, 9185, 9186, 9188, 9189, 9190, 9191, 9192, 9195, 9196, 9198, 9199,
        9200,
        9201, 9202, 9205, 9206, 9208, 9209, 9210, 9211, 9212, 9215, 9216, 9218, 9219, 9220, 9221, 9222, 9225, 9226,
        9228,
        9229, 9250, 9251, 9252, 9255, 9256, 9258, 9259, 9260, 9261, 9262, 9265, 9266, 9268, 9269, 9280, 9281, 9282,
        9285,
        9286, 9288, 9289, 9290, 9291, 9292, 9295, 9296, 9298, 9299, 9500, 9501, 9502, 9505, 9506, 9508, 9509, 9510,
        9511,
        9512, 9515, 9516, 9518, 9519, 9520, 9521, 9522, 9525, 9526, 9528, 9529, 9550, 9551, 9552, 9555, 9556, 9558,
        9559,
        9560, 9561, 9562, 9565, 9566, 9568, 9569, 9580, 9581, 9582, 9585, 9586, 9588, 9589, 9590, 9591, 9592, 9595,
        9596,
        9598, 9599, 9600, 9601, 9602, 9605, 9606, 9608, 9609, 9610, 9611, 9612, 9615, 9616, 9618, 9619, 9620, 9621,
        9622,
        9625, 9626, 9628, 9629, 9650, 9651, 9652, 9655, 9656, 9658, 9659, 9660, 9661, 9662, 9665, 9666, 9668, 9669,
        9680,
        9681, 9682, 9685, 9686, 9688, 9689, 9690, 9691, 9692, 9695, 9696, 9698, 9699, 9800, 9801, 9802, 9805, 9806,
        9808,
        9809, 9810, 9811, 9812, 9815, 9816, 9818, 9819, 9820, 9821, 9822, 9825, 9826, 9828, 9829, 9850, 9851, 9852,
        9855,
        9856, 9858, 9859, 9860, 9861, 9862, 9865, 9866, 9868, 9869, 9880, 9881, 9882, 9885, 9886, 9888, 9889, 9890,
        9891,
        9892, 9895, 9896, 9898, 9899, 9900, 9901, 9902, 9905, 9906, 9908, 9909, 9910, 9911, 9912, 9915, 9916, 9918,
        9919,
        9920, 9921, 9922, 9925, 9926, 9928, 9929, 9950, 9951, 9952, 9955, 9956, 9958, 9959, 9960, 9961, 9962, 9965,
        9966,
        9968, 9969, 9980, 9981, 9982, 9985, 9986, 9988, 9989, 9990, 9991, 9992, 9995, 9996, 9998, 9999]


left, right = 0, 2320
while left < right:
    print(left, right)
    mid = (left + right) // 2
    if nums[mid] > N:
        right = mid-1
    elif nums[mid] <= N:
        left = mid+1
left
